// @algorithm @lc id=44 lang=cpp 
// @title wildcard-matching


// #define print(...)
// @test("","")=true
// @test("","*")=true
// @test("","*a")=false
// @test("aa","a")=false
// @test("aa","*")=true
// @test("cb","?a")=false
// @test("adceb","*a*b")=true
// @test("acdcb","a*c?b")=false
class Solution {
public:
    bool isMatch(string s, string p) {
        int sn = s.size(), pn = p.size();
        vector<vector<bool>> sp(sn+1, vector<bool>(pn+1));
        sp[0][0] = true;
        for(int j=0; j<pn; j++){
            if('*'!=p[j]) break;
            sp[0][j+1] = true;
        }
        for(int i=1; i<=sn; i++){
            for(int j=1; j<=pn; j++){
                if('*' == p[j-1])
                    sp[i][j] = sp[i][j-1] || sp[i-1][j];
                else if('?' == p[j-1] || s[i-1] == p[j-1])
                    sp[i][j] = sp[i-1][j-1];
            }
        }
        return sp[sn][pn];
    }
};